DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2017.22

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Authors: Jacob Focke, Nicole Megow, and Julie Meißner

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract

We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.

Cite as

Jacob Focke, Nicole Megow, and Julie Meißner. Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{focke_et_al:LIPIcs.SEA.2017.22,
  author =	{Focke, Jacob and Megow, Nicole and Mei{\ss}ner, Julie},
  title =	{{Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.22},
  URN =		{urn:nbn:de:0030-drops-76202},
  doi =		{10.4230/LIPIcs.SEA.2017.22},
  annote =	{Keywords: MST, explorable uncertainty, competitive ratio, experimental algorithms}
}

Search Results

Documents authored by Focke, Jacob

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Abstract

Cite as

Thanks for your feedback!

Could not send message